package Offer026;

import java.util.ArrayList;
import java.util.List;

/**
 * 重排链表
 *
 * @author 23737
 * @time 2021.12.11
 */
public class Test {
    public static void main(String[] args) {

    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

/**
 * 使用list进行存储
 */
class Solution {
    public void reorderList(ListNode head) {
        List<ListNode> list = new ArrayList<>();
        ListNode listNode = head;
        while(listNode != null){
            list.add(listNode);
            listNode = listNode.next;
        }
        int i = 0;
        int j = list.size() - 1;
        while(i < j){
            list.get(i).next = list.get(j);
            i++;
            if(i == j){
                break;
            }
            list.get(j).next = list.get(i);
            j--;
        }
        //这里要将最后一个元素的next指向为空，不然就会出现链表成环
        list.get(i).next = null;
    }
}
